package dataStructure.Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author lhn
 * @date 2024-04-21 14:14
 */

public class Calculator {
    public static void main(String[] args) {
//        String expression = "3+2*6-2";
//        String expression = "3-1-1";
        String expression = "  (70+2*6)-4/2";
//        String expression = "  (70+2*6)-4/0";
        // 去除字符串中的空格
        expression = expression.replaceAll("\\s", "");
        //创建数栈和符号栈
        ArrayStackEx numStack = new ArrayStackEx(10);
        ArrayStackEx operStack = new ArrayStackEx(10);
//        calculate(expression, numStack, operStack);
        //带小括号的表达式计算在calculate2中
        calculate2(expression,numStack,operStack);
    }
    public static void calculate(String expression, ArrayStackEx numStack, ArrayStackEx operStack) {
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int operator = 0;
        int res = 0;
        char ch = ' ';  //每次扫描得到的char放入
        String keepNum = "";    //用于拼接多位数
        while (true) {
            //这个取值感觉可以用正则放到数组中再取
            ch = expression.substring(index,index+1).charAt(0);
            //判断是否为运算符
            if (operStack.isOperator(ch)) {
                if (operStack.isEmpty()) {
                    //如果发现当前的符号栈为空,就直接入栈
                    operStack.push(ch);
                } else {
                    //如果符号栈有操作符,就进行比较
                    //如果当前的操作符的优先级小于或者等于栈中
                    //的操作符,就需要从数栈中pop出两个数,在从符号栈中pop出一个符号,进行运算,
                    //将得到结果,入数栈,然后将当前的操作符入符号栈,如果当前的操作符的优先级大
                    //于栈中的操作符,就直接入符号栈.
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        operator = operStack.pop();
                        res = operStack.cal(num1, num2, operator);
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                }
            } else {
//                numStack.push(ch - '0');
                //处理多位数
                keepNum += ch;
                //如果ch已经是expression的最后一位，就直接入栈
                if (index==expression.length()-1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是否为数字，如果是数字，就继续扫描，如果是运算符则入栈
                    if (operStack.isOperator(expression.substring(index+1,index+2).charAt(0))){
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            }
            index ++;
            if (index >= expression.length()) {
                break;
            }
        }
        //表达式扫描完毕，就按顺序使用数栈和符号栈中的内容
        while (true) {
            //如果符号栈为空，计算最后的结果，数栈中只有最后的结果
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            operator = operStack.pop();
            res = numStack.cal(num1,num2,operator);
            numStack.push(res);
        }
        System.out.printf("%s 的计算结果为 %d\n",expression,res);
    }
    public static void calculate2(String expression, ArrayStackEx numStack, ArrayStackEx operStack) {
        // 用于匹配数值和运算符的正则表达式
        String Regex = "(\\d+)|([()+\\-*/])";
        // 编译正则表达式
        Pattern pattern = Pattern.compile(Regex);
        // 创建Matcher对象
        Matcher matcher = pattern.matcher(expression);
        int num1 = 0;
        int num2 = 0;
        int operator = 0;
        int res = 0;
        while (matcher.find()) {
            if (matcher.group(1) != null) {
                //匹配到数字
                numStack.push(Integer.parseInt(matcher.group(1)));
            } else if (matcher.group(2) != null) {
                //匹配到运算符
                char op = matcher.group(2).charAt(0); // 获取匹配的单个字符
                if (op == '(') {
                    // 左括号特殊处理，压入运算符栈
                    operStack.push(op);
                } else if (op == ')') {
                    //遇到右括号时，不断从数字栈中弹出操作数，从运算符栈中
                    //弹出运算符并计算结果，直到遇到左括号为止（左括号不弹出）。
                    while (!operStack.isEmpty()) {
                        operator = operStack.pop();
                        if (operator == '(') {
                            // 遇到左括号，括号内的运算已处理完毕，退出循环
                            break;
                        }
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        res = operStack.cal(num1, num2, operator);
                        numStack.push(res);
                    }
                } else {
                    // 普通的运算符，压入运算符栈
                    //如果符号栈有操作符,就进行比较
                    //如果当前的操作符的优先级小于或者等于栈中
                    //的操作符,就需要从数栈中pop出两个数,在从符号栈中pop出一个符号,进行运算,
                    //将得到结果,入数栈,然后将当前的操作符入符号栈,如果当前的操作符的优先级大
                    //于栈中的操作符,就直接入符号栈.
                    if (operStack.isEmpty() || operStack.priority(op) > operStack.priority(operStack.peek())) {
                        // 当前操作符的优先级大于栈顶操作符，或栈为空，直接入符号栈
                        operStack.push(op);
                    } else {
                        // 当前操作符的优先级小于或等于栈顶操作符
                        while (!operStack.isEmpty() && operStack.priority(op) <= operStack.priority(operStack.peek()) && operStack.peek() != '(') {
                            operator = operStack.pop();
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            res = operStack.cal(num1, num2, operator); // 调用独立的计算函数
                            numStack.push(res);
                        }
                        // 无论是否进行了运算，都将当前操作符压入符号栈
                        operStack.push(op);
                    }
                }
            }

        }
        //表达式扫描完毕，就按顺序使用数栈和符号栈中的内容
        while (true) {
            //如果符号栈为空，计算最后的结果，数栈中只有最后的结果
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            operator = operStack.pop();
            res = numStack.cal(num1,num2,operator);
            numStack.push(res);
        }
        System.out.printf("%s 的计算结果为 %d\n",expression,res);
    }
}
//使用数组模拟的栈
class ArrayStackEx extends ArrayStack {
    public ArrayStackEx(int maxSize) {
        super(maxSize);
    }
    //返回运算符的优先级
    public int priority(int operator) {
        if (operator == '(') {
            return 2;
        } else if(operator == '*' || operator == '/') {
            return 1;
        } else if (operator == '+' || operator =='-'){
            return 0;
        } else {
            return -1;
        }
    }
    //判断是否为运算符
    public boolean isOperator(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' || val == ')';
    }
    //计算方法
    public int cal(int num1, int num2, int operator) {
        int res = 0; //result
        //后弹出的数 operator 先弹出的数
        switch (operator) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;  //顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                if (num1 == 0) {
                    throw new RuntimeException("表达式有问题");
                }
                res = num2 / num1;
                break;
        }
        return res;
    }
}